home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1996 June / EnigmA AMIGA RUN 08 (1996)(G.R. Edizioni)(IT)[!][issue 1996-06][EARSAN CD VII].iso / earcd / gcc / ixemlsrc.lha / ixemul / ixnet / page.c < prev    next >
C/C++ Source or Header  |  1996-03-13  |  22KB  |  893 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)page.c      5.13 (Berkeley) 6/17/91";
  39. #endif /* LIBC_SCCS and not lint */
  40. #undef DEBUG
  41. /******************************************************************************
  42. PACKAGE:  hashing
  43.  
  44. DESCRIPTION:
  45.     Page manipulation for hashing package.
  46.  
  47. ROUTINES:
  48.     External
  49.     __get_page
  50.     __add_ovflpage
  51.     Internal
  52.     overflow_page
  53.     open_temp
  54. ******************************************************************************/
  55. #define KERNEL
  56. #include "ixnet.h"
  57. #include <sys/param.h>
  58. #include <fcntl.h>
  59. #include <signal.h>
  60. #include <errno.h>
  61. #include <db.h>
  62. #include <stdio.h>
  63. #include <stdlib.h>
  64. #include <string.h>
  65. #include <unistd.h>
  66. #include "hash.h"
  67. #include "page.h"
  68. #include "utils.h"
  69.  
  70. #define assert(x) \
  71. { \
  72.     if(!x) {\
  73.     fprintf(stderr,"assertion failed on line %d, in file %s\n",__LINE__,__FILE__); \
  74.     exit(1);\
  75.     }\
  76. }
  77.  
  78. /* Externals */
  79. /* buf.c */
  80.  
  81. /* my internals */
  82. static u_short overflow_page();
  83. static int open_temp();
  84. static int ugly_split();
  85. static void squeeze_key();
  86. static void putpair();
  87. static u_long *fetch_bitmap();
  88.  
  89. #ifdef HASH_STATISTICS
  90. extern long hash_accesses, hash_collisions, hash_expansions, hash_overflows;
  91. #endif
  92. #define PAGE_INIT(P)                                    \
  93. {                            \
  94.     ((u_short *)P)[0] = 0;                              \
  95.     ((u_short *)P)[1] = hashp->BSIZE - 3 * sizeof(u_short);     \
  96.     ((u_short *)P)[2] = hashp->BSIZE;                   \
  97. }
  98.  
  99. /*
  100.     This is called AFTER we have verified that there is room on the
  101.     page for the pair (PAIRFITS has returned true) so we go right
  102.     ahead and start moving stuff on.
  103. */
  104. static void
  105. putpair(p, key, val)
  106. char *p;
  107. DBT *key;
  108. DBT *val;
  109. {
  110.     register u_short n;
  111.     register u_short off;
  112.     register u_short *bp = (u_short *) p;
  113.  
  114. /* enter the key first */
  115.     n = bp[0];
  116.  
  117.     off = OFFSET(bp) - key->size;
  118.     bcopy( key->data, p+off, key->size );
  119.     bp[++n] = off;
  120.  
  121. /* now the data */
  122.     off -= val->size;
  123.     bcopy(val->data,  p + off, val->size);
  124.     bp[++n] = off;
  125.  
  126. /* adjust page info */
  127.     bp[0] = n;
  128.     bp[n+1] = off - ((n+3)*sizeof(u_short));
  129.     bp[n+2] = off;
  130.     return;
  131. }
  132. /*
  133.     0 OK
  134.     -1 error
  135. */
  136. extern int
  137. __delpair(bufp, ndx)
  138. BUFHEAD *bufp;
  139. register int ndx;
  140. {
  141.     register u_short *bp = (u_short *) bufp->page;
  142.     register int n = bp[0];
  143.     register u_short newoff;
  144.     u_short pairlen;
  145.  
  146.     if ( bp[ndx+1] < REAL_KEY ) return ( __big_delete ( bufp, ndx ) );
  147.     if ( ndx != 1 ) newoff = bp[ndx-1];
  148.     else newoff = hashp->BSIZE;
  149.     pairlen = newoff - bp[ndx+1];
  150.  
  151.     if ( ndx != (n-1) ) {
  152.         /* Hard Case -- need to shuffle keys */
  153.         register int i;
  154.         register char *src = bufp->page + (int)OFFSET(bp);
  155.         register char *dst = src + (int)pairlen;
  156.         bcopy ( src, dst, bp[ndx+1] - OFFSET(bp) );
  157.  
  158.         /* Now adjust the pointers */
  159.         for ( i = ndx+2; i <= n; i += 2 ) {
  160.             if ( bp[i+1]  == OVFLPAGE ) {
  161.             bp[i-2] = bp[i];
  162.             bp[i-1] = bp[i+1];
  163.             } else {
  164.             bp[i-2] = bp[i] + pairlen;
  165.             bp[i-1] = bp[i+1] + pairlen;
  166.             }
  167.         }
  168.     }
  169.  
  170.     /* Finally adjust the page data */
  171.     bp[n] = OFFSET(bp) + pairlen;
  172.     bp[n-1] = bp[n+1] + pairlen + 2 * sizeof(u_short);
  173.     bp[0] = n-2;
  174.     hashp->NKEYS--;
  175.  
  176.     bufp->flags |= BUF_MOD;
  177.     return (0);
  178. }
  179. /*
  180.     -1 ==> Error
  181.     0 ==> OK
  182. */
  183. extern int
  184. __split_page(obucket, nbucket)
  185. u_int obucket;
  186. u_int nbucket;
  187. {
  188.     DBT key;
  189.     DBT val;
  190.  
  191.     register BUFHEAD *new_bufp;
  192.     register BUFHEAD *old_bufp;
  193.     register u_short *ino;
  194.     register char    *np;
  195.     int n;
  196.     int ndx;
  197.     int retval;
  198.     char    *op;
  199.  
  200.     u_short copyto = (u_short)hashp->BSIZE;
  201.     u_short diff;
  202.     u_short off = (u_short)hashp->BSIZE;
  203.     u_short moved;
  204.  
  205.     old_bufp = __get_buf ( obucket, NULL, 0 );
  206.     new_bufp = __get_buf ( nbucket, NULL, 0 );
  207.  
  208.     old_bufp->flags |= (BUF_MOD|BUF_PIN);
  209.     new_bufp->flags |= (BUF_MOD|BUF_PIN);
  210.  
  211.     ino = (u_short *)(op = old_bufp->page);
  212.     np = new_bufp->page;
  213.  
  214.     moved = 0;
  215.  
  216.     for (n = 1, ndx = 1; n < ino[0]; n+=2) {
  217.         if ( ino[n+1] < REAL_KEY ) {
  218.             retval = ugly_split( obucket, old_bufp, new_bufp,
  219.                      copyto, moved );
  220.             old_bufp->flags &= ~BUF_PIN;
  221.             new_bufp->flags &= ~BUF_PIN;
  222.             return(retval);
  223.  
  224.         }
  225.         key.data = (u_char *)op + ino[n];
  226.         key.size = off - ino[n];
  227.  
  228.         if ( __call_hash ( key.data, key.size ) == obucket ) {
  229.             /* Don't switch page */
  230.             diff = copyto - off;
  231.             if ( diff ) {
  232.             copyto = ino[n+1] + diff;
  233.             bcopy ( op + ino[n+1], op + copyto,  off-ino[n+1]);
  234.             ino[ndx] = copyto + ino[n] - ino[n+1];
  235.             ino[ndx+1] = copyto;
  236.             } else copyto = ino[n+1];
  237.             ndx += 2;
  238.         } else {
  239.             /* Switch page */
  240.             val.data = (u_char *)op + ino[n+1];
  241.             val.size = ino[n] - ino[n+1];
  242.             putpair( np, &key, &val);
  243.             moved +=2;
  244.         }
  245.  
  246.         off = ino[n+1];
  247.     }
  248.  
  249.     /* Now clean up the page */
  250.     ino[0] -= moved;
  251.     FREESPACE(ino) = copyto - sizeof(u_short) * (ino[0]+3);
  252.     OFFSET(ino) = copyto;
  253.  
  254. #ifdef DEBUG3
  255.     fprintf(stderr, "split %d/%d\n",
  256.            ((u_short *) np)[0] / 2,
  257.            ((u_short *) op)[0] / 2);
  258. #endif
  259.     /* unpin both pages */
  260.     old_bufp->flags &= ~BUF_PIN;
  261.     new_bufp->flags &= ~BUF_PIN;
  262.     return(0);
  263. }
  264. /*
  265.     0 ==> success
  266.     -1 ==> failure
  267.  
  268.     Called when we encounter an overflow or big key/data page during
  269.     split handling.
  270.     This is special cased since we have to begin checking whether
  271.     the key/data pairs fit on their respective pages and because
  272.     we may need overflow pages for both the old and new pages
  273.  
  274.     The first page might be a page with regular key/data pairs
  275.     in which case we have a regular overflow condition and just
  276.     need to go on to the next page or it might be a big key/data
  277.     pair in which case we need to fix the big key/data pair.
  278. */
  279. static int
  280. ugly_split( obucket, old_bufp, new_bufp, copyto, moved )
  281. u_int    obucket;    /* Same as __split_page */
  282. BUFHEAD *old_bufp;
  283. BUFHEAD *new_bufp;
  284. u_short copyto;     /* First byte on page which contains key/data values */
  285. int    moved;        /* number of pairs moved to new page */
  286. {
  287.     register BUFHEAD *bufp = old_bufp;        /* Buffer header for ino */
  288.     register u_short    *ino = (u_short *)old_bufp->page;
  289.                         /* Page keys come off of */
  290.     register u_short    *np = (u_short *)new_bufp->page;        /* New page */
  291.     register u_short    *op = (u_short *)old_bufp->page;
  292.                         /* Page keys go on to if they
  293.                            aren't moving */
  294.  
  295.     char    *cino;                /* Character value of ino */
  296.     BUFHEAD    *last_bfp = NULL;        /* Last buffer header OVFL which
  297.                            needs to be freed */
  298.     u_short    n;
  299.     u_short    off, ov_addr = 0;
  300.  
  301.     DBT key, val;
  302.     SPLIT_RETURN    ret;
  303.  
  304.     n = ino[0]-1;
  305.     while ( n < ino[0] ) {
  306.     if ( ino[2] < REAL_KEY && ino[2] != OVFLPAGE ) {
  307.         if (__big_split (old_bufp, new_bufp, bufp, ov_addr, obucket, &ret)) {
  308.         return(-1);
  309.         }
  310.         old_bufp = ret.oldp;
  311.         if ( !old_bufp ) return(-1);
  312.         op = (u_short *)old_bufp->page;
  313.         new_bufp = ret.newp;
  314.         if ( !new_bufp ) return(-1);
  315.         np = (u_short *)new_bufp->page;
  316.         bufp = ret.nextp;
  317.         if ( !bufp ) return(0);
  318.         cino = (char *)bufp->page;
  319.         ino = (u_short *)cino;
  320.         last_bfp = ret.nextp;
  321.     } else if ( ino[n+1] == OVFLPAGE ) {
  322.         ov_addr = ino[n];
  323.         /*
  324.         Fix up the old page -- the extra 2 are the fields which
  325.         contained the overflow information
  326.         */
  327.         ino[0] -= (moved + 2);
  328.         FREESPACE(ino) = copyto - sizeof(u_short) * (ino[0]+3);
  329.         OFFSET(ino) = copyto;
  330.  
  331.         bufp = __get_buf ( ov_addr, bufp, 0 );
  332.         if ( !bufp ) return(-1);
  333.  
  334.         ino = (u_short *)bufp->page;
  335.         n = 1;
  336.         copyto = hashp->BSIZE;
  337.         moved = 0;
  338.  
  339.         if ( last_bfp ) {
  340.         __free_ovflpage( last_bfp);
  341.         }
  342.         last_bfp = bufp;
  343.     }
  344.  
  345.  
  346.     /* Move regular sized pairs of there are any */
  347.     off = hashp->BSIZE;
  348.     for ( n = 1; (n < ino[0]) && (ino[n+1] >= REAL_KEY); n += 2 ) {
  349.         cino = (char *)ino;
  350.         key.data = (u_char *)cino + ino[n];
  351.         key.size = off - ino[n];
  352.         val.data = (u_char *)cino + ino[n+1];
  353.         val.size = ino[n] - ino[n+1];
  354.         off = ino[n+1];
  355.  
  356.         if ( __call_hash ( key.data, key.size ) == obucket ) {
  357.         /* Keep on old page */
  358.         if (PAIRFITS(op,(&key),(&val))) putpair((char *)op, &key, &val);
  359.         else {
  360.             old_bufp = __add_ovflpage ( old_bufp );
  361.             if ( !old_bufp ) return(-1);
  362.             op = (u_short *)old_bufp->page;
  363.             putpair ((char *)op, &key, &val);
  364.         }
  365.         old_bufp->flags |= BUF_MOD;
  366.         } else {
  367.         /* Move to new page */
  368.         if (PAIRFITS(np,(&key),(&val))) putpair((char *)np, &key, &val);
  369.         else {
  370.             new_bufp = __add_ovflpage ( new_bufp );
  371.             if ( !new_bufp )return(-1);
  372.             np = (u_short *)new_bufp->page;
  373.             putpair ((char *)np, &key, &val);
  374.         }
  375.         new_bufp->flags |= BUF_MOD;
  376.         }
  377.     }
  378.     }
  379.     if ( last_bfp ) {
  380.     __free_ovflpage(last_bfp);
  381.     }
  382.  
  383.     return (0);
  384. }
  385. /*
  386.     Add the given pair to the page
  387.     1 ==> failure
  388.     0 ==> OK
  389. */
  390. extern int
  391. __addel(bufp, key, val)
  392. BUFHEAD *bufp;
  393. DBT    *key;
  394. DBT    *val;
  395. {
  396.     register u_short *bp = (u_short *)bufp->page;
  397.     register u_short *sop;
  398.     int do_expand;
  399.  
  400.     do_expand = 0;
  401.     while ( bp[0] &&  (bp[bp[0]] < REAL_KEY) ) {
  402.     /* Exception case */
  403.     if ( bp[2] < REAL_KEY ) {
  404.         /* This is a big-keydata pair */
  405.         bufp = __add_ovflpage(bufp);
  406.         if ( !bufp ) {
  407.         return(-1);
  408.         }
  409.         bp = (u_short *)bufp->page;
  410.     } else {
  411.         /* Try to squeeze key on this page */
  412.         if ( FREESPACE(bp) > PAIRSIZE(key,val) ) {
  413.         squeeze_key ( bp, key, val );
  414.         return(0);
  415.         } else {
  416.         bufp = __get_buf ( bp[bp[0]-1], bufp, 0 );
  417.         if (!bufp) {
  418.             return(-1);
  419.         }
  420.         bp = (u_short *)bufp->page;
  421.         }
  422.     }
  423.     }
  424.  
  425.     if ( PAIRFITS(bp,key,val) ) putpair (bufp->page, key, val);
  426.     else {
  427.     do_expand = 1;
  428.     bufp = __add_ovflpage ( bufp );
  429.     if (!bufp)return(-1);
  430.     sop = (u_short *) bufp->page;
  431.  
  432.     if ( PAIRFITS(sop, key, val) ) putpair ( (char *)sop, key, val );
  433.     else if ( __big_insert ( bufp, key, val ) ) {
  434.         return(-1);
  435.     }
  436.     }
  437.     bufp->flags |= BUF_MOD;
  438.     /*
  439.     If the average number of keys per bucket exceeds the fill factor,
  440.     expand the table
  441.     */
  442.     hashp->NKEYS++;
  443.     if (do_expand ||
  444.     (hashp->NKEYS / (hashp->MAX_BUCKET+1) > hashp->FFACTOR) ) {
  445.      return(__expand_table());
  446.     }
  447.     return(0);
  448. }
  449.  
  450. /*
  451.     returns a pointer, NULL on error
  452. */
  453. extern BUFHEAD *
  454. __add_ovflpage ( bufp )
  455. BUFHEAD *bufp;
  456. {
  457.     register    u_short *sp = (u_short *)bufp->page;
  458.  
  459.     u_short    ovfl_num;
  460.     u_short    ndx;
  461. #ifdef DEBUG1
  462.     int tmp1, tmp2;
  463. #endif
  464.  
  465.     bufp->flags |= BUF_MOD;
  466.     ovfl_num = overflow_page ();
  467. #ifdef DEBUG1
  468.     tmp1 = bufp->addr;
  469.     tmp2 = bufp->ovfl?bufp->ovfl->addr:0;
  470. #endif
  471.     if (!ovfl_num || !(bufp->ovfl = __get_buf ( ovfl_num, bufp, 1 ))) {
  472.     return(NULL);
  473.     }
  474.     bufp->ovfl->flags |= BUF_MOD;
  475. #ifdef DEBUG1
  476.     fprintf ( stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", tmp1, tmp2,
  477.         bufp->ovfl->addr );
  478. #endif
  479.     ndx = sp[0];
  480.     /*
  481.     Since a pair is allocated on a page only if there's room
  482.     to add an overflow page, we know that the OVFL information
  483.     will fit on the page
  484.     */
  485.     sp[ndx+4] = OFFSET(sp);
  486.     sp[ndx+3] = FREESPACE(sp) - OVFLSIZE;
  487.     sp[ndx+1] = ovfl_num;
  488.     sp[ndx+2] = OVFLPAGE;
  489.     sp[0] = ndx+2;
  490. #ifdef HASH_STATISTICS
  491.         hash_overflows++;
  492. #endif
  493.     return(bufp->ovfl);
  494. }
  495.  
  496. /*
  497.     0 indicates SUCCESS
  498.     -1 indicates FAILURE
  499. */
  500. int
  501. __get_page ( p, bucket, is_bucket, is_disk, is_bitmap )
  502. char    *p;
  503. u_int    bucket;
  504. int    is_bucket;
  505. int    is_disk;
  506. int    is_bitmap;
  507. {
  508.     register int size;
  509.     register int fd;
  510.     register int page;
  511.     u_short    *bp;
  512.     int     rsize;
  513.  
  514.     fd = hashp->fp;
  515.     size = hashp->BSIZE;
  516.  
  517.     if ( (fd == -1) || !is_disk ) {
  518.     PAGE_INIT(p);
  519.     return(0);
  520.     }
  521.  
  522.     if ( is_bucket) page = BUCKET_TO_PAGE (bucket);
  523.     else page = OADDR_TO_PAGE (bucket);
  524.     if ((lseek ( fd, page << hashp->BSHIFT, SEEK_SET ) == -1) ||
  525.     ((rsize = read ( fd, p, size )) == -1 )) {
  526.     return(-1);
  527.     }
  528.     bp = (u_short *)p;
  529.     if ( !rsize ) {
  530.     bp[0] = 0;        /* We hit the EOF, so initialize a new page */
  531.     } else if ( rsize != size ) {
  532.     errno = EFTYPE;
  533.     return(-1);
  534.     }
  535.     if (!bp[0]) {
  536.     PAGE_INIT(p);
  537.     } else if ( hashp->LORDER != BYTE_ORDER ) {
  538.     register int i;
  539.     register int max;
  540.  
  541.     if ( is_bitmap ) {
  542.         max = hashp->BSIZE >> 2;    /* divide by 4 */
  543.         for ( i=0; i < max; i++ ) {
  544.         BLSWAP(((long *)p)[i]);
  545.         }
  546.     } else {
  547.         BSSWAP(bp[0]);
  548.         max = bp[0] + 2;
  549.         for ( i=1; i <= max; i++ ) {
  550.         BSSWAP(bp[i]);
  551.         }
  552.     }
  553.     }
  554.     return (0);
  555. }
  556.  
  557. /*
  558.     Write page p to disk
  559.     -1==>failure
  560.     0==> OK
  561. */
  562. int
  563. __put_page ( p, bucket, is_bucket, is_bitmap )
  564. char    *p;
  565. u_int    bucket;
  566. int    is_bucket;
  567. int    is_bitmap;
  568. {
  569.     register int size;
  570.     register int fd;
  571.     register int page;
  572.     int wsize;
  573.  
  574.     size = hashp->BSIZE;
  575.     if ( (hashp->fp == -1) && open_temp() ) return (1);
  576.     fd = hashp->fp;
  577.  
  578.     if ( hashp->LORDER != BYTE_ORDER ) {
  579.     register int i;
  580.     register int max;
  581.  
  582.     if ( is_bitmap ) {
  583.         max = hashp->BSIZE >> 2;    /* divide by 4 */
  584.         for ( i=0; i < max; i++ ) {
  585.         BLSWAP(((long *)p)[i]);
  586.         }
  587.     } else {
  588.         max = ((u_short *)p)[0] + 2;
  589.         for ( i=0; i <= max; i++ ) {
  590.         BSSWAP(((u_short *)p)[i]);
  591.         }
  592.     }
  593.     }
  594.     if (is_bucket ) page = BUCKET_TO_PAGE (bucket);
  595.     else page = OADDR_TO_PAGE ( bucket );
  596.     if ((lseek ( fd, page << hashp->BSHIFT, SEEK_SET ) == -1) ||
  597.     ((wsize = write ( fd, p, size )) == -1 )) {
  598.     /* Errno is set */
  599.     return(-1);
  600.     }
  601.     if ( wsize != size ) {
  602.     errno = EFTYPE;
  603.     return(-1);
  604.     }
  605.     return(0);
  606. }
  607. #define BYTE_MASK    ((1 << INT_BYTE_SHIFT) -1)
  608. /*
  609.     Initialize a new bitmap page.  Bitmap pages are left in memory
  610.     once they are read in.
  611. */
  612. u_long *
  613. __init_bitmap(pnum, nbits, ndx)
  614. u_short pnum;
  615. int    nbits;
  616. int    ndx;
  617. {
  618.     u_long    *ip;
  619.     int     clearints;
  620.     int     clearbytes;
  621.  
  622.     if ( !(ip = (u_long *)malloc (hashp->BSIZE)) ) return (NULL);
  623.     hashp->nmaps++;
  624.     clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1;
  625.     clearbytes = clearints << INT_TO_BYTE;
  626.     memset ((char *)ip, 0, clearbytes );
  627.     memset ( ((char *) ip) + clearbytes, 0xFF,
  628.         hashp->BSIZE-clearbytes );
  629.     ip[clearints-1] = ALL_SET << (nbits & BYTE_MASK);
  630.     SETBIT(ip, 0);
  631.     hashp->BITMAPS[ndx] = pnum;
  632.     hashp->mapp[ndx] = ip;
  633.     return(ip);
  634. }
  635. static int
  636. first_free ( map )
  637. u_long map;
  638. {
  639.     register u_long     mask;
  640.     register u_long     i;
  641.  
  642.     mask = 0x1;
  643.     for ( i=0; i < BITS_PER_MAP; i++ ) {
  644.     if ( !(mask & map) ) return(i);
  645.     mask = mask << 1;
  646.     }
  647.     return ( i );
  648. }
  649.  
  650. static u_short
  651. overflow_page ( )
  652. {
  653.     register    int max_free;
  654.     register    int splitnum;
  655.     register    u_long *freep = NULL;
  656.     register    int offset;
  657.     u_short    addr;
  658.     int     in_use_bits;
  659.     int     free_page, free_bit;
  660.     int     i, j, bit;
  661. #ifdef DEBUG2
  662.     int tmp1, tmp2;
  663. #endif
  664.  
  665.     splitnum = __log2(hashp->MAX_BUCKET);
  666.     max_free = hashp->SPARES[splitnum];
  667.  
  668.     free_page = (max_free-1) >> (hashp->BSHIFT + BYTE_SHIFT);
  669.     free_bit  = (max_free-1) & ((hashp->BSIZE << BYTE_SHIFT) - 1);
  670.  
  671.     /* Look through all the free maps to find the first free block */
  672.     for ( i = 0; i <= free_page; i++ ) {
  673.     if (!(freep = (u_long *)hashp->mapp[i])  &&
  674.         !(freep = fetch_bitmap(i)) ) {
  675.         return ( NULL );
  676.     }
  677.     if ( i == free_page ) in_use_bits = free_bit;
  678.     else in_use_bits = (hashp->BSIZE << BYTE_SHIFT) -1;
  679.  
  680.     for (j = 0, bit = 0; bit <= in_use_bits; j++, bit += BITS_PER_MAP ) {
  681.          if ( freep[j] != ALL_SET ) goto found;
  682.     }
  683.     }
  684.     /* No Free Page Found */
  685.     hashp->SPARES[splitnum]++;
  686.     offset = hashp->SPARES[splitnum] -
  687.          (splitnum ? hashp->SPARES[splitnum-1] : 0);
  688.  
  689.     /* Check if we need to allocate a new bitmap page */
  690.     if ( free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1 ) {
  691.     free_page++;
  692. #define OVMSG    "hash: out of overflow pages; increase page size\n"
  693.     if ( free_page >= NCACHED ) {
  694.         (void) write (STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
  695.         return(NULL);
  696.     }
  697.     /*
  698.         This is tricky.  The 1 indicates that you want the
  699.         new page allocated with 1 clear bit.  Actually, you
  700.         are going to allocate 2 pages from this map.  The first
  701.         is going to be the map page, the second is the overflow
  702.         page we were looking for.  The init_bitmap routine
  703.         automatically, sets the first bit of itself to indicate
  704.         that the bitmap itself is in use.  We would explicitly
  705.         set the second bit, but don't have to if we tell init_bitmap
  706.         not to leave it clear in the first place.
  707.     */
  708.     __init_bitmap ( OADDR_OF(splitnum, offset), 1, free_page );
  709.     hashp->SPARES[splitnum]++;
  710. #ifdef DEBUG2
  711.     free_bit = 2;
  712. #endif
  713.     offset++;
  714.     } else {
  715.     /*
  716.         Free_bit addresses the last used bit.  Bump it to
  717.         address the first available bit.
  718.     */
  719.     free_bit++;
  720.     SETBIT ( freep, free_bit );
  721.     }
  722.  
  723.     /* Calculate address of the new overflow page */
  724.     if ( offset > SPLITMASK ) {
  725.     (void) write (STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
  726.     return(NULL);
  727.     }
  728.     addr = OADDR_OF(splitnum, offset);
  729. #ifdef DEBUG2
  730.     fprintf ( stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
  731.         addr, free_bit, free_page );
  732. #endif
  733.     return(addr);
  734.  
  735. found:
  736.     bit = bit + first_free(freep[j]);
  737.     SETBIT(freep,bit);
  738. #ifdef DEBUG2
  739.     tmp1 = bit;
  740.     tmp2 = i;
  741. #endif
  742.     /*
  743.     Bits are addressed starting with 0, but overflow pages are
  744.     addressed beginning at 1. Bit is a bit addressnumber, so we
  745.     need to increment it to convert it to a page number.
  746.     */
  747.     bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT));
  748.  
  749.     /* Calculate the split number for this page */
  750.     for ( i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++ );
  751.     offset =(i ? bit - hashp->SPARES[i-1] : bit );
  752.     if ( offset >= SPLITMASK ) return(NULL);/* Out of overflow pages */
  753.     addr = OADDR_OF(i, offset);
  754. #ifdef DEBUG2
  755.     fprintf ( stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
  756.         addr, tmp1, tmp2 );
  757. #endif
  758.  
  759.     /* Allocate and return the overflow page */
  760.     return (addr);
  761. }
  762.  
  763. /*
  764.     Mark this overflow page as free.
  765. */
  766. void
  767. __free_ovflpage ( obufp )
  768. BUFHEAD *obufp;
  769. {
  770.     register u_short addr = obufp->addr;
  771.     int free_page, free_bit;
  772.     int bit_address;
  773.     u_short ndx;
  774.     u_long *freep;
  775.  
  776. #ifdef DEBUG1
  777.     fprintf ( stderr, "Freeing %d\n", addr );
  778. #endif
  779.     ndx = (((u_short)addr) >> SPLITSHIFT);
  780.     bit_address = (ndx ? hashp->SPARES[ndx-1] : 0) + (addr & SPLITMASK) - 1;
  781.     free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT));
  782.     free_bit  = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1);
  783.  
  784.     if ( !(freep = hashp->mapp[free_page]) &&
  785.      !(freep = fetch_bitmap( free_page )) ) {
  786.     /*
  787.         This had better never happen.  It means we tried to
  788.         read a bitmap that has already had overflow pages allocated
  789.         off it, and we failed to read it from the file
  790.     */
  791.     assert(0);
  792.     }
  793.     CLRBIT(freep, free_bit);
  794. #ifdef DEBUG2
  795.     fprintf ( stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n",
  796.         obufp->addr, free_bit, free_page );
  797. #endif
  798.     __reclaim_buf ( obufp );
  799. }
  800.  
  801. /*
  802. 0 success
  803. -1 failure
  804. */
  805. static int
  806. open_temp()
  807. {
  808.     sigset_t    set, oset;
  809.     static char namestr[] = "_hashXXXXXX";
  810.  
  811.     /* Block signals; make sure file goes away at process exit. */
  812.     sigemptyset(&set);
  813.     sigaddset(&set, SIGHUP);
  814.     sigaddset(&set, SIGINT);
  815.     sigaddset(&set, SIGQUIT);
  816.     sigaddset(&set, SIGTERM);
  817.     (void)sigprocmask(SIG_BLOCK, &set, &oset);
  818.     if ((hashp->fp = mkstemp ( namestr )) != -1) {
  819.     (void)unlink(namestr);
  820.     (void)fcntl(hashp->fp, F_SETFD, 1);
  821.     }
  822.     (void)sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL);
  823.     return(hashp->fp != -1 ? 0 : -1);
  824. }
  825.  
  826. /*
  827.     We have to know that the key will fit, but the
  828.     last entry on the page is an overflow pair, so we
  829.     need to shift things.
  830. */
  831. static void
  832. squeeze_key ( sp, key, val )
  833. u_short *sp;
  834. DBT    *key;
  835. DBT    *val;
  836. {
  837.     register    char    *p = (char *)sp;
  838.     u_short    free_space, off;
  839.     u_short    pageno, n;
  840.  
  841.     n = sp[0];
  842.     free_space = FREESPACE(sp);
  843.     off = OFFSET(sp);
  844.  
  845.     pageno = sp[n-1];
  846.     off -= key->size;
  847.     sp[n-1] = off;
  848.     bcopy ( key->data, p + off, key->size );
  849.     off -= val->size;
  850.     sp[n] = off;
  851.     bcopy ( val->data, p + off, val->size );
  852.     sp[0] = n+2;
  853.     sp[n+1] = pageno;
  854.     sp[n+2] = OVFLPAGE;
  855.     FREESPACE(sp) = free_space - PAIRSIZE(key,val);
  856.     OFFSET(sp) = off;
  857. }
  858.  
  859. static u_long *
  860. fetch_bitmap ( ndx )
  861. int    ndx;
  862. {
  863.     if ( ndx >= hashp->nmaps  ||
  864.     !(hashp->mapp[ndx] = (u_long *)malloc ( hashp->BSIZE )) ||
  865.      __get_page ((char *)hashp->mapp[ndx], hashp->BITMAPS[ndx], 0, 1, 1)) {
  866.  
  867.         return(NULL);
  868.     }
  869.     return ( hashp->mapp[ndx] );
  870. }
  871. #ifdef DEBUG4
  872. print_chain ( addr )
  873. short    addr;
  874. {
  875.     BUFHEAD *bufp;
  876.     short    *bp;
  877.     short    oaddr;
  878.  
  879.     fprintf ( stderr, "%d ", addr );
  880.     bufp = __get_buf ( (int)addr, NULL, 0 );
  881.     bp = (short *)bufp->page;
  882.     while ( bp[0] &&
  883.         ((bp[bp[0]] == OVFLPAGE) ||
  884.          ((bp[0] > 2) && bp[2] < REAL_KEY))) {
  885.         oaddr = bp[bp[0]-1];
  886.         fprintf ( stderr, "%d ", (int)oaddr );
  887.         bufp = __get_buf ( (int)oaddr, bufp, 0 );
  888.         bp = (short *)bufp->page;
  889.     }
  890.     fprintf ( stderr, "\n" );
  891. }
  892. #endif
  893.